package com.code.leetcode.center50.树的遍历;

import com.code.leetcode.utils.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/26 11:55
 */
public class The105 {

    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int idx = 0;
        int len = preorder.length - 1;
        for (int num : inorder) {
            map.put(num, idx++);
        }
        return helper(preorder,inorder, 0, len, 0, len);
    }

    public TreeNode helper(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre_left]);
        int index = map.get(preorder[pre_left]);
        int len = index - in_left;
        node.left = helper(preorder, inorder, pre_left + 1, pre_left + len, in_left, index - 1);
        node.right = helper(preorder, inorder, pre_left + 1, pre_right, index + 1, in_right);
        return node;
    }

}
